#!/usr/bin/env python3
# -*- coding:utf-8 -*-
## author : cypro666
## date   : 2014.5.18
"""
A group of functions and classes implement some useful algorithms
note all functions and classes is not thread-safe, wrap it if need.
"""
import sys
import random
import operator
import array 
from itertools import *

__all__ = ['dotproduct', 'advance', 'ntake', 'foreach2', 'untilfail', 'nth',
           'quantify', 'seqcycles', 'flatten', 'funrepeater', 'pairwise', 'grouper', 
           'roundrobin', 'everseen', 'everseen', 'randselect',
           'BivTable', 'BisectList']


def dotproduct(vec1, vec2):
    return sum(map(operator.mul, vec1, vec2))


def advance(iterator, n):
    next(islice(iterator, n, n), None)


def ntake(iterable, start, n):
    return islice(iterable, start, start + n, 1)


def foreach2(fun1, fun2, iterable):
    for i in iterable:
        fun2(fun1(i))


def untilfail(fun, exception, iterable, *args):
    n = 0
    try:
        for i in iterable:
            fun(i, *args)
            n += 1
    except exception:
        pass
    return n


def nth(iterable, n, default = None):
    return next(islice(iterable, n, None), default)


def quantify(iterable, pred = bool):
    return sum(map(pred, iterable))


def seqcycles(iterable, n):
    return chain.from_iterable(repeat(tuple(iterable), n))


def flatten(nested):
    return chain.from_iterable(nested)


def funrepeater(fun, times = None, *args):
    if times is None:
        return starmap(fun, repeat(args))
    return starmap(fun, repeat(args, times))


def pairwise(iterable):
    a, b = tee(iterable)
    next(b, None)
    return zip(a, b)


def grouper(iterable, n, fillvalue = None):
    args = [iter(iterable)] * n
    return zip_longest(fillvalue=fillvalue, *args)


def roundrobin(*iterables):
    pending = len(iterables)
    nexts = cycle(iter(it).__next__ for it in iterables)
    while pending:
        try:
            for thenext in nexts:
                yield thenext()
        except StopIteration:
            pending -= 1
            nexts = cycle(islice(nexts, pending))


def everseen(iterable, key=None):
    seen = set()
    seen_add = seen.add
    if key is None:
        for element in filterfalse(seen.__contains__, iterable):
            seen_add(element)
            yield element
    else:
        for element in iterable:
            k = key(element)
            if k not in seen:
                seen_add(k)
                yield element


def justseen(iterable, key=None):
    return map(next, map(operator.itemgetter(1), groupby(iterable, key)))


def randselect(iterable, n):
    pool = tuple(iterable)
    indices = sorted(random.sample(range(len(pool)), n))
    return tuple(pool[i] for i in indices)



class BivTable(object):
    """A biv table supports k->v and v->k query, note all keys and values must be unique"""
    __slots__ = ('__kv', '__vk', '__hasher')
    def __init__(self, keyhasher = None):
        super().__init__()
        self.__kv = {}
        self.__vk = {}
        self.__hasher = keyhasher
    
    def __str__(self):
        return '%s\n%s' % (self.__kv, self.__vk)

    def __len__(self):
        assert len(self.__kv) == len(self.__vk)
        return len(self.__kv)
    
    def size(self):
        return (self.__len__(), sys.getsizeof(self))
    
    def clear(self):
        self.__kv.clear()
        del self.__kv
        self.__kv = {}
        self.__vk.clear()
        del self.__vk
        self.__vk = {}
    
    def iterkv(self):
        return iter(self.__kv.items())
    
    def itervk(self):
        return iter(self.__vk.items())
    
    def zip(self):
        return zip(self.__kv, self.__vk)

    def haskey(self, key):
        if self.__hasher:
            return self.__hasher(key) in self.__kv
        return key in self.__kv
    
    def hasval(self, val):
        return val in self.__vk
    
    def __contains__(self, obj):
        if self.__hasher:
            if self.__hasher(obj) in self.__kv:
                return True
        elif obj in self.__kv:
            return True
        if obj in self.__vk:
            return True
        return False
    
    def getval(self, key):
        if self.__hasher:
            return self.__kv.get(self.__hasher(key))
        return self.__kv[key]
    
    def getkey(self, val):
        return self.__vk[val]
    
    def __getitem__(self, obj):
        try:
            if self.__hasher:
                return self.__kv[self.__hasher(obj)]
            return self.__kv[obj]
        except KeyError:
            try:
                return self.__vk[obj]
            except KeyError:
                raise KeyError('BivTable : can not find obj!')
    
    def __setitem__(self, key, val):
        if self.__hasher:
            key = self.__hasher(key)
        if (val in self.__vk) and (key != self.__vk[val]):
            raise ValueError('BivTable : duplicate key or val {%s:%s}' % (key, val))
        if key in self.__kv:
            self.__vk.pop(self.__kv[key])
        self.__kv[key] = val
        self.__vk[val] = key
        assert len(self.__kv) == len(self.__vk)
    
    def update(self, key, val):
        self.__setitem__(key, val)
        
    def fromiter(self, iterable):
        self.clear()
        try:
            for k, v in iterable:
                self.__setitem__(k, v)
        except Exception as e:
            self.clear()
            raise e



class BisectList(list):
    __slots__ = ()
    """A list that can keep order after inserted, combines bisect and list"""
    def __init__(self, *args, **kwargs):
        super().__init__(*args, **kwargs)
    
    def makeset(self):
        return set(self)
    
    def makedict(self, aggregate = False):
        if not aggregate:
            return dict(enumerate(self))
        grouper = {}
        for index, val in enumerate(self):
            if val not in grouper:
                grouper[val] = array.array('L')
            grouper[val].append(index)
        return grouper
    
    def binary_search(self, x):
        lo = 0
        hi = self.__len__()
        while lo < hi:
            mid = (lo + hi) >> 1
            if self[mid] > x:
                lo = mid + 1
            else:
                if self[mid] == x:
                    return mid
                hi = mid
            return -1

    def bisect(self, x, lo = 0, hi = None, right = False):
        if lo < 0:
            raise ValueError('lo must be non-negative')
        if hi is None:
            hi = self.__len__()
        if right:
            while lo < hi:
                mid = (lo + hi) >> 1
                if self[mid] > x: 
                    hi = mid
                else: 
                    lo = mid + 1
        else:
            while lo < hi:
                mid = (lo + hi) >> 1
                if self[mid] < x: 
                    lo = mid + 1
                else: 
                    hi = mid
        return lo
    
    def insort(self, x, lo = 0, hi = None, right = False):
        pos = self.bisect(x, lo, hi, right)
        self.insert(pos, x)
        return pos


from .debug import time_meter

@time_meter(__name__)
def test():
    s = ['aa', 'bb', 'cc', 'dd', 'ee']
    p = [1, 3, 5, 7, 9]
    q = [0, 2, 4, 6, 8]
    a = [11,22,33]
    ll = [[1,2], [3,4], (5, 6)]
    def fun(x):
        print(x * 2, end=' ')
        return x * 2
    
    print('dotproduct', dotproduct(p, q))
    i = iter(s)
    advance(i, 3)
    print('advance', next(i)) 
    print('ntake', list(ntake(s, 0, 2)))
    print('foreach2', end=' ')
    foreach2(fun, fun, a)
    print()
    n = untilfail(fun, StopIteration, iter(q))
    print('untilfail', n)
    print('nth', nth(s, 3, "none"), nth(s, 8, "none"))
    print('quantify', quantify(q, bool))
    print('seqcycles', list(seqcycles(s, 2)))
    print('flatten', list(flatten(ll)))
    print('funrepeater', list(funrepeater(random.random, 3)))
    print('pairwise', list(pairwise(list(range(5)))))
    print('groupby', list(grouper(p, 2, None)))
    print('roundrobin', list(roundrobin(s, p, q)))
    print('justseen', list(everseen("AAABBCCDDDDEFABC", key=None)))
    print('everseen', list(justseen("AAABBCCDDDDEFABC", key=None)))
    print('randselect', randselect(s, 3))
    
    d = [('name1', 'Mike'), ('name2', 'Jerry'), ('tag', 2.4), ('base', (1,2,3))]
    bt = BivTable(keyhasher = None)
    bt.fromiter(d)
    print(bt, len(bt))
    try:
        print(bt.getval('name1'))
        print(bt.getkey(2.4))
        bt['name2'] = 'Ops'
        print(bt['name2'])
        bt.update('bingo', 'Cherry')
        bt.update('Cherry', 'bingo')
        bt.update('tag', 'bingo')
    except Exception as e:
        print(e)
    print(bt)
    assert bt.haskey('base')
    assert bt.hasval((1,2,3))
    assert 'name1' in bt
    assert 'name3' not in bt
    import time
    t = time.time()
    for i in range(1000000):
        bt[i] = 1000000 + (i + 1)
    print(time.time()-t)
    t = time.time()
    dd = {}
    ddd = {}
    for i in range(1000000):
        dd[i] = 1000000 + (i + 1)
    for i in range(1000000):
        dd[i] = 1000000 + (i + 1)
    print(time.time()-t)
    print(bt.size())

    sl = BisectList()
    for i in range(100000):
        sl.append(random.randint(1,100000))
    sl.sort()
    print(len(sl))
    t = time.time()    
    for i in range(100000, 200000):
        assert sl.binary_search(i) == -1
    print(time.time() - t)
    t = time.time()    
    for i in range(10000):
        sl.insort(i)
        sl.insort(i, right=True)
    print(time.time() - t)
    tmp = sl[:]
    sl.sort()
    for i in range(100000):
        assert tmp[i] == sl[i]
    t = time.time()    
    s = sl.makeset()
    print(len(s))
    print(time.time() - t)
    t = time.time()    
    d = sl.makedict(False)
    print(len(d))
    print(time.time() - t)
    t = time.time()    
    d = sl.makedict(True)
    print(len(d))
    print(time.time() - t)



